<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.13"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>OpenMesh: How to navigate on a mesh</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtreedata.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript">
  $(document).ready(initResizable);
</script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
<link href="logo_align.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td id="projectlogo"><img alt="Logo" src="rwth_vci_rgb.jpg"/></td>
  <td id="projectalign" style="padding-left: 0.5em;">
   <div id="projectname">OpenMesh
   </div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.13 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
<script type="text/javascript" src="menudata.js"></script>
<script type="text/javascript" src="menu.js"></script>
<script type="text/javascript">
$(function() {
  initMenu('',true,false,'search.php','Search');
  $(document).ready(function() { init_search(); });
});
</script>
<div id="main-nav"></div>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
  <div id="nav-tree">
    <div id="nav-tree-contents">
      <div id="nav-sync" class="sync"></div>
    </div>
  </div>
  <div id="splitbar" style="-moz-user-select:none;" 
       class="ui-resizable-handle">
  </div>
</div>
<script type="text/javascript">
$(document).ready(function(){initNavTree('a04330.html','');});
</script>
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div class="header">
  <div class="headertitle">
<div class="title">How to navigate on a mesh </div>  </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><h1><a class="anchor" id="nav_overview"></a>
Overview</h1>
<ul>
<li><a class="el" href="a04330.html#nav_intro">Introduction</a> </li>
<li><a class="el" href="a04330.html#nav_he">Navigating over halfedges</a> </li>
<li><a class="el" href="a04330.html#nav_bound">Mesh boundaries</a> </li>
<li><a class="el" href="a04330.html#nav_io">Using incoming and outgoing halfedges</a> </li>
<li><a class="el" href="a04330.html#nav_opposite">Using opposite halfedges</a> </li>
<li><a class="el" href="a04330.html#nav_to_from">Getting the to and from vertices</a></li>
</ul>
<h1><a class="anchor" id="nav_intro"></a>
Introduction</h1>
<p>In this tutorial you will learn how to navigate on a mesh using the OpenMesh library. In the previous chapter (see <a class="el" href="a04328.html">Mesh Iterators and Circulators</a>) you have learned how to iterate over vertices, edges, halfedges and faces as well as circulate over certain structures such as 1-rings and many more. So in this tutorial we will focus on efficiently using the halfedge data structure and some very useful attributes such as the boundary flag. We assume that you already made yourself familiar with the halfedge structure which is used in OpenMesh. Further information on this topic can be found in <a class="el" href="a04322.html">The Halfedge Data Structure</a>.</p>
<h1><a class="anchor" id="nav_he"></a>
Navigating over halfedges</h1>
<p>So let's start with navigating over halfedges of a mesh. Assume we have the following mesh topology:</p>
<div class="image">
<img src="mesh.normal.png" alt="mesh.normal.png"/>
</div>
<p>We can now select an arbitrary halfedge of this mesh which then offers either one of two possible navigations:</p>
<ul>
<li>If the chosen halfedge lies at a boundary or in other words is not adjacent to a face, we can now navigate along the boundary (or hole) of our mesh by using <code>next_halfedge_handle()</code> or <code>prev_halfedge_handle()</code>:</li>
</ul>
<div class="image">
<img src="mesh.outer.png" alt="mesh.outer.png"/>
</div>
<ul>
<li>If the chosen halfedge is adjacent to a face, we can then navigate along all halfedges that are adjacent to this face. In other words we circulate around the inner halfedges of one face:</li>
</ul>
<div class="image">
<img src="mesh.inner.png" alt="mesh.inner.png"/>
</div>
<p>In both cases the code would look something like the following example. Depending on whether the initial halfedge is adjacent to a face or not, we will either navigate on the boundary halfedges of our mesh or along the inner halfedges of a face: </p><div class="fragment"><div class="line">[...]</div><div class="line"></div><div class="line">TriMesh::HalfedgeHandle heh, heh_init;</div><div class="line"></div><div class="line"><span class="comment">// Get the halfedge handle assigned to vertex[0]</span></div><div class="line">heh = heh_init = mesh.halfedge_handle(vertex[0].handle());</div><div class="line"></div><div class="line"><span class="comment">// heh now holds the handle to the initial halfedge.</span></div><div class="line"><span class="comment">// We now get further on the boundary by requesting</span></div><div class="line"><span class="comment">// the next halfedge adjacent to the vertex heh</span></div><div class="line"><span class="comment">// points to...</span></div><div class="line">heh = mesh.next_halfedge_handle(heh);</div><div class="line"></div><div class="line"><span class="comment">// We can do this as often as we want:</span></div><div class="line"><span class="keywordflow">while</span>(heh != heh_init) {</div><div class="line">        heh = mesh.next_halfedge_handle(heh);</div><div class="line">}</div><div class="line"></div><div class="line">[...]</div></div><!-- fragment --><p>References:<br />
 <a class="el" href="a01877.html#ad0719d8eacf8a0281327398a231c06a7" title="Get the next halfedge handle. ">OpenMesh::Concepts::KernelT&lt; FinalMeshItems &gt;::next_halfedge_handle()</a><br />
 <a class="el" href="a01877.html#a004adf582bbb98f5723c505f4e6363ed" title="Get the previous halfedge of the given halfedge. ">OpenMesh::Concepts::KernelT&lt; FinalMeshItems &gt;::prev_halfedge_handle()</a></p>
<h1><a class="anchor" id="nav_bound"></a>
Mesh boundaries</h1>
<p>As you have seen in the previous section, navigating along boundaries is very simple. In general OpenMesh also offers a boundary attribute for edges, vertices and faces. So testing i.e. whether a face is a boundary face is quite simple using <a class="el" href="a02313.html#ac86d2e4ea8f50b75876b35b175c4c635" title="Check if the halfedge is at the boundary. ">OpenMesh::PolyConnectivity::is_boundary()</a>.<br />
</p>
<dl class="section note"><dt>Note</dt><dd>You can iterate along boundaries by using the next_halfedge_handle(). If you are on a boundary, the next halfedge is guaranteed to be also a boundary halfedge.</dd></dl>
<p>So for each type we can make use of one of the following functions:</p>
<div class="fragment"><div class="line"><span class="comment">// Test if a halfedge lies at a boundary (is not adjacent to a face)</span></div><div class="line"><span class="keywordtype">bool</span> is_boundary (HalfedgeHandle _heh) <span class="keyword">const</span></div><div class="line"></div><div class="line"><span class="comment">// Test if an edge lies at a boundary</span></div><div class="line"><span class="keywordtype">bool</span> is_boundary (EdgeHandle _eh) <span class="keyword">const</span></div><div class="line"></div><div class="line"><span class="comment">// Test if a vertex is adjacent to a boundary edge</span></div><div class="line"><span class="keywordtype">bool</span> is_boundary (VertexHandle _vh) <span class="keyword">const</span></div><div class="line"></div><div class="line"><span class="comment">// Test if a face has at least one adjacent boundary edge.</span></div><div class="line"><span class="comment">// If _check_vertex=true, this function also tests if at least one</span></div><div class="line"><span class="comment">// of the adjacent vertices is a boundary vertex</span></div><div class="line"><span class="keywordtype">bool</span> is_boundary (FaceHandle _fh, <span class="keywordtype">bool</span> _check_vertex=<span class="keyword">false</span>) const</div></div><!-- fragment --><h1><a class="anchor" id="nav_io"></a>
Using incoming and outgoing halfedges</h1>
<p>OpenMesh offers quite a lot of iterators and circulators to easily iterate over the structures of a mesh. A very helpful iterator is the <a class="el" href="a02313.html#a46a18bcbc8b8e47bddc0b88d5365aca7" title="Enumerates incoming half edges in a clockwise fashion. ">OpenMesh::PolyConnectivity::VertexIHalfedgeIter</a> or the <a class="el" href="a02313.html#a54440c9f054667eb51d4246b81b4fccf" title="Enumerates outgoing half edges in a clockwise fashion. ">OpenMesh::PolyConnectivity::VertexOHalfedgeIter</a> which are used to iterate over all incoming/outgoing halfedges of a vertex. So, sticking to the illustration below, a OpenMesh::PolyConnectivity:V:ertexIHalfedgeIter for the lower most vertex would iterate over all incoming halfedges (blue), whereas the OpenMesh::PolyConnectivity::OpenMesh::PolyConnectivity::VertexOHalfedgeIter would iterate over all outgoing halfedges (red):</p>
<div class="image">
<img src="mesh.inout.png" alt="mesh.inout.png"/>
</div>
<p>A schematic code example of how to use the halfedge iterators as described above: </p><div class="fragment"><div class="line">[...]</div><div class="line"></div><div class="line"><span class="comment">// Get some vertex handle</span></div><div class="line"><a class="code" href="a02389.html#a0fc18e13d70825938274e3faf7b55e01">PolyMesh::VertexHandle</a> v = ...;</div><div class="line"></div><div class="line"><span class="keywordflow">for</span>(<a class="code" href="a02389.html#a437621f3901a93d0ebf8cdceac8e2939">PolyMesh::VertexIHalfedgeIter</a> vih_it = mesh.vih_iter(v); vih_it; ++vih_it) {</div><div class="line">        <span class="comment">// Iterate over all incoming halfedges...</span></div><div class="line">}</div><div class="line"></div><div class="line"><span class="keywordflow">for</span>(<a class="code" href="a02389.html#a6549eda743520c8a7aa3dfe6a37b2468">PolyMesh::VertexOHalfedgeIter</a> voh_it = mesh.voh_iter(v); voh_it; ++voh_it) {</div><div class="line">        <span class="comment">// Iterate over all outgoing halfedges...</span></div><div class="line">}</div><div class="line"></div><div class="line">[...]</div></div><!-- fragment --><h1><a class="anchor" id="nav_opposite"></a>
Using opposite halfedges</h1>
<p>The halfedge structure splits every edge into two directional parts by creating two directed edges out of one undirected edge. So for every halfedge there exists its counterpart pointing in the opposite direction. OpenMesh allows to easily navigate through opposing halfedges via the function <a class="el" href="a01877.html#a6a226814fdd62a6b9885d210bc9a27ee" title="Get the opposite halfedge. ">OpenMesh::Concepts::KernelT&lt; FinalMeshItems &gt;::opposite_halfedge_handle()</a>. So in the illustration below <code>opposite_halfedge_handle()</code> for the blue halfedge would return the red halfedge:</p>
<div class="image">
<img src="mesh.opp.png" alt="mesh.opp.png"/>
</div>
<p>Use this function as described in the example below:</p>
<div class="fragment"><div class="line"><span class="comment">// Get the halfedge handle of i.e. the halfedge</span></div><div class="line"><span class="comment">// that is associated to the first vertex</span></div><div class="line"><span class="comment">// of our set of vertices</span></div><div class="line">PolyMesh::HalfedgeHandle heh = mesh.halfedge_handle(*(mesh.vertices_begin()));</div><div class="line"></div><div class="line"><span class="comment">// Now get the handle of its opposing halfedge</span></div><div class="line">PolyMesh::HalfedgeHandle opposite_heh = mesh.opposite_halfedge_handle(heh);</div></div><!-- fragment --><p>There are also a few more functions that offer easy access to opposing structures:</p>
<div class="fragment"><div class="line"><span class="comment">// Get the face adjacent to the opposite halfedge</span></div><div class="line"><a class="code" href="a02313.html#ad0e146d46ca485644ba9e52d51dd7fe4">OpenMesh::PolyConnectivity::opposite_face_handle</a>();</div><div class="line"></div><div class="line"><span class="comment">// Get the handle to the opposite halfedge</span></div><div class="line"><a class="code" href="a01877.html#a6a226814fdd62a6b9885d210bc9a27ee">OpenMesh::Concepts::KernelT::opposite_halfedge_handle</a>();</div><div class="line"></div><div class="line"><span class="comment">// Get the opposite vertex to the opposite halfedge</span></div><div class="line"><a class="code" href="a02481.html#a5ec59830d43d6b3799e404111e8b0f4b">OpenMesh::TriConnectivity::opposite_he_opposite_vh</a>();</div><div class="line"></div><div class="line"><span class="comment">// Get the vertex assigned to the opposite halfedge</span></div><div class="line"><a class="code" href="a02481.html#a64fd0a14a44fb140b70cff81ee6956fd">OpenMesh::TriConnectivity::opposite_vh</a>();</div></div><!-- fragment --><h1><a class="anchor" id="nav_to_from"></a>
Getting the to and from vertices</h1>
<div class="image">
<img src="mesh.to.from.png" alt="mesh.to.from.png"/>
</div>
<p>If you have an halfedge, you can get the to and the from handles of the adjacent vertices. </p><dl class="section note"><dt>Note</dt><dd>The halfedges have a direction. Therefore the to vertex is the from vertex of the opposite halfedge and vice versa.</dd></dl>
<div class="fragment"><div class="line"><span class="comment">// Get the handle of the to vertex</span></div><div class="line"><a class="code" href="a01877.html#afedeab1bff0b6f7198bf16c449b64499">OpenMesh::Concepts::KernelT::to_vertex_handle</a>();</div><div class="line"></div><div class="line"><span class="comment">// Get the handle of the from vertex</span></div><div class="line"><a class="code" href="a01877.html#adb6b8b163fd2e0e28a0510d50c236333">OpenMesh::Concepts::KernelT::from_vertex_handle</a>();</div></div><!-- fragment --> </div></div><!-- contents -->
</div><!-- doc-content -->
<hr>
<address>
<small>
<a href="http://www.rwth-graphics.de" style="text-decoration:none;">
</a>
Project <b>OpenMesh</b>, 
&copy;&nbsp; Computer Graphics Group, RWTH Aachen.
Documentation generated using 
<a class="el" href="http://www.doxygen.org/index.html">
<b>doxygen</b>
</a>.
</small>
</address>
</body>
</html>
